#include <stdio.h>

void swap(int* x, int* y) {
    int tem = *x;
    *x = *y;
    *y = tem;
}

void adjustHeap(int* arr, int parent, int n) {
    int child = parent * 2 + 1;
    while (child < n) {
        if (child + 1 < n && arr[child] < arr[child + 1]) {
            child++;
        }
        if (arr[child] > arr[parent]) {
            swap(&arr[child], &arr[parent]);
            parent = child;
            child = parent * 2 + 1;
        }
        else {
            break;
        }
    }
}

void heapsort(int* arr, int n) {
    for (int i = (n - 2) / 2; i >= 0; i--) {
        adjustHeap(arr, i, n);
    }
    for (int i = n - 1; i > 0; i--) {
        swap(&arr[0], &arr[i]);
        adjustHeap(arr, 0, i);
    }
}


int main() {
    int arr[] = {4,6,8,5,9,10 };
    int n = sizeof(arr) / sizeof(arr[0]);
    heapsort(arr, n);
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    return 0;
}